package com.yun.algorithmproblem.leetcode;

import java.util.Arrays;

/**
 * 3218. 切蛋糕的最小总开销 I
 * <p>
 * 有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。
 * <p>
 * 给你整数 m ，n 和两个数组：
 * <p>
 * horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
 * verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
 * 一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：
 * <p>
 * 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
 * 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。
 * 每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
 * <p>
 * 每次操作的开销都为最开始对应切割线的开销，并且不会改变。
 * <p>
 * 请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
 */
public class Leetcode3218 {

    public static void main(String[] args) {
        Leetcode3218 obj = new Leetcode3218();
        int m=3,n=2;
        int[] horizontalCut=new int[]{1,3};
        int[] verticalCut=new int[]{5};
        int cnt = obj.minimumCost(m, n, horizontalCut, verticalCut);
        System.out.println(cnt);
    }

    public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        int cnt = 0;
        int hMul = 1, vtMul = 1;
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        int p = m - 2, q = n - 2;
        while (p >= 0 && q >= 0) {
            int h = horizontalCut[p];
            int v = verticalCut[q];
            if (h > v) {
                cnt += h * hMul;
                vtMul++;
                p--;
            } else {
                cnt += v * vtMul;
                hMul++;
                q--;
            }
        }
        for (int i = p; i >= 0 ; i--) {
            cnt+=horizontalCut[i]*hMul;
        }
        for (int i = q; i >= 0; i--) {
            cnt+=verticalCut[i]*vtMul;
        }
        return cnt;
    }
}
